//给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。 
//
// 你应当保留两个分区中每个节点的初始相对位置。 
//
// 示例: 
//
// 输入: head = 1->4->3->2->5->2, x = 3
//输出: 1->2->2->4->3->5
// 
// Related Topics 链表 双指针 
// 👍 248 👎 0

package leetcode.editor.cn;

//Java：分隔链表
public class P86PartitionList {

    /*
     *
     * 思路： 原本是利用双指针遍历链表，符合要求的移动到左指针，但是总是写bug。 现在是建两个虚拟结点，遍历的时候移动到各自结点
     *
     * 执行用时： 0 ms , 在所有 Java 提交中击败了 100.00% 的用户 内存消耗： 39.2 MB , 在所有 Java 提交中击败了 75.20% 的用户
     *
     */
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode(int x) { val = x; }
     * }
     */

    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }


    class Solution {
        public ListNode partition(ListNode head, int x) {
            if (head == null) {
                return null;
            }
            // 先建两个虚拟头结点
            ListNode node1 = new ListNode(0);   // 小的
            ListNode node2 = new ListNode(0);   // 大的
            ListNode node1Temp = node1;   // 大的
            ListNode node2Temp = node2;   // 大的

            // [0] 1 4 3 2 5 2    3
            while (head != null) {
                ListNode temp = head.next;
                head.next = null;
                if (head.val < x) {
                    node1.next = head;
                    node1 = node1.next;
                } else {
                    node2.next = head;
                    node2 = node2.next;
                }
                head = temp;
            }
            node1.next = node2Temp.next;
            return node1Temp.next;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    public static void main(String[] args) {
        Solution solution = new P86PartitionList().new Solution();
        ListNode node2 = new ListNode(2);
        node2 = add(node2, 5);
        node2 = add(node2, 2);
        node2 = add(node2, 3);
        node2 = add(node2, 4);
        node2 = add(node2, 1);
        System.out.println(solution.partition(node2, 3));
        // TO TEST
    }

    private static ListNode add(ListNode listNode, int x) {
        ListNode node = new ListNode(x);
        node.next = listNode;
        return node;
    }

}